\documentclass[unicode]{beamer}
\mode<presentation>
\usepackage{beamerthemesplit}
\usetheme{Malmoe}
\usepackage[cp1251]{inputenc}
\usepackage[russian,english]{babel}
\usepackage[T2A]{fontenc}
\usepackage{amssymb,amsfonts,amsmath}
\usepackage {array}
\usepackage{graphicx}
\usepackage {gastex}
\usepackage{algorithm,algpseudocode}
\newtheorem {teo} {Theorem}
\usepackage[]{color}%,dvips
\DeclareMathOperator{\per}{per}
\DeclareMathOperator{\lexp}{lexp}
\def\U{_\infty^{\phantom{i}a}T}
%\usepackage{times}
\usepackage{pstricks,pst-node,pst-text}%,pst-3d
\usepackage{wrapfig,floatflt}%,nccfloats
\definecolor{emp}{rgb}{0.2, 0.4, 0.4}
\definecolor{tr}{rgb}{0,0.5,0}
\definecolor{gr}{rgb}{0, 0, 1}
\definecolor{orng}{rgb}{1, 0.5, 0}
\definecolor{rd} {rgb} {1,0,0}


\algtext*{EndWhile}% Remove "end while" text
\algtext*{EndIf}% Remove "end if" text
\algtext*{EndFunction}% Remove "end function" text
\algtext*{EndProcedure}% Remove "end procedure" text
\algtext*{EndFor}% Remove "end for" text

\let\OldComment\Comment
\renewcommand{\Comment}[1]{\OldComment{\textcolor{gray}{#1}}}



\author[D. Kosolobov, M. Rubinchik]{Dmitry Kosolobov, Mikhail Rubinchik}
\title[All Distinct Subpalindromes Online]{An Optimal Online Algorithm for Finding All Distinct Subpalindromes of a String}

\institute[]{Ural Federal University}
\begin{document}
\date{ }
\maketitle

\section{Definitions and Problem}

\begin{frame}
\frametitle{Introduction}
\begin{itemize}
\item<1-> A \emph{palindrome} is a string that is equal to its reversal. For example the string ``aabcbaa'' is a palindrome.
\item<2-> A \emph{subpalindrome} of a string is a substring that is a palindrome.
\end{itemize}
\vspace{1em}
\begin{itemize}
\item<3-> The well-known \emph{Sturmian words} are characterized by their palindromic complexity (de Luca (1997), Droubay, Pirillo, (1999)).
\item<3-> The \emph{rich words} are studied by Glen, Justin, Widmer, Zambony (2009) (a word $w$ with $|w|{+}1$ distinct subpalindromes is called \emph{rich}).
\item<3-> The class of rich words includes the \emph{episturmian words} introduced by Droubay, Justin, Pirillo (2001).
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Problem}
\uncover<2->{
It is known that every string of length $n$ contains at most $n{+}1$ distinct subpalindromes, including the empty string (Droubay, Justin, Pirillo. 2001).}
\vspace{1em}

\uncover<3->{\textbf{Can one find all distinct subpalindromes of a string in linear time and space?}}

\vspace{1em}
\uncover<4->{This question was answered in the affirmative, but with an offline algorithm (Groult, Prieur, Richomme, 2010). The authors stated the existence of the corresponding online algorithm as an open problem.}
\end{frame}

\section{Main Result}

\begin{frame}
\begin{theorem}
Let $\Sigma$ be a finite unordered (resp., ordered) alphabet. There exists an online algorithm which finds all distinct subpalindromes in a string over $\Sigma$ in $O(n|\Sigma|)$ (resp., $O(n\log|\Sigma|)$) time and linear space. This algorithm is optimal in the comparison based computation model.
\end{theorem}
\end{frame}

\begin{frame}
\begin{lemma}
The set of all distinct subpalindromes of a string coincides with the set of longest palindromic suffixes of all prefixes of this string.
\end{lemma}

\vspace{1em}
\textit{Example.} The set of all subpalindromes of ``aacba'' is \{a,b,c,aa\}.
\begin{tabular}{ll}
\textbf{prefix} & \textbf{longest palindromic suffix}\\
a & a\\
aa & aa\\
aac & c\\
aacb & b\\
aacba & a
\end{tabular}
\end{frame}

\begin{frame}
\frametitle{Manacher's algorithm (1975)}
\begin{itemize}
\item<2-> A palindrome of even (resp. odd) length is referred to as an \emph{even} (resp. \emph{odd}) palindrome.
\item<3-> If $w$ is a subpalindrome of the string $v = swu$, then the number $|s| + \lfloor |w|/2\rfloor$ is the \emph{center} of  $w$.
\item<4-> The number $\lfloor |w|/2\rfloor$ is the \emph{radius} of the palindrome $w$.
\item<5-> Manacher's algorithm for odd (resp. even) palindromes computes online for the string $text[1..n]$ the array $Rad[1..n]$ such that $Rad[j]$ is the radius of the longest odd (resp. even) subpalindrome of $text[1..n]$ centered at $j$.
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Manacher's algorithm pseudocode}
The following modification of Manacher's algorithm computes online the longest odd palindromic suffix of a string. The algorithm for even case is analogous.
\begin{algorithmic}[1]
	\Procedure{AddLetter}{$c$}
	\EndProcedure
		\State $s \gets i{-}Rad[i]$\Comment{$i$ is the center of $text[1..n]$ max odd suf-pal} \label{lst:line:calcs}
        \State $text[n{+}1] \gets c$ \Comment{append $c$ to $text[1..n]$}
		\While{$i{+}Rad[i] \leqslant n$}\label{lst:line:forbeg}
			\State $Rad[i] \gets \min(Rad[s{+}n{-}i], n{-}i)$\Comment{$Rad[i]$ in $text[1..n]$}\label{lst:line:min}
			\If{$i + Rad[i] = n \mathrel{\mathbf{and}} text[i{-}Rad[i]{-}1] = c$}\label{lst:line:breadth}
				\State $Rad[i] \gets Rad[i] + 1$\Comment{extending the max suf-pal}
				\State $\mathbf{break}$     \Comment{max odd suf-pal of $text[1..n{+}1]$ found}
			\EndIf
            \State $i \gets i + 1$ \Comment{next candidate for the center of max odd suf-pal}
		\EndWhile\label{lst:line:forend}
		\State $n \gets n + 1$ \Comment{$i$ is the center of max odd suf-pal of $text[1..n]$}
\end{algorithmic}
\end{frame}

\begin{frame}
\frametitle{Example}
Consider the string $w=abadaac$ and the sequence of calls $AddLetter(w[j])$, $j=1..7$. After the $n$-th step the string $text[i{-}Rad[i]..n]$ is the longest odd palindromic suffix of $text[1..n]$.

\hrulefill

\begin{tabular}{lllll}
n & $text[1..n]$ & $text[i{-}Rad[i]..n]$ & $i$ & $Rad$\\
1 & a & a & 1 & (0)\\
2 & ab & b & 2 & (0,0)\\
3 & aba & aba & 2 & (0,1)\\
4 & abad & d & 4 & (0,1,0,0)\\
5 & abada & ada & 4 & (0,1,0,1)\\
6 & abadaa & a & 6 & (0,1,0,1,0,0)\\
7 & abadaac & c & 7 & (0,1,0,1,0,0,0)
\end{tabular}
\end{frame}

\begin{frame}
Manacher's algorithm finds all subpalindromes of a string. To find all \textcolor{red}{distinct} subpalindromes, we have to verify whether the maximal suffix-palindrome of a string has another occurrence in this string.

\vspace{1em}
We will use a version of suffix tree known as \emph{Ukkonen's tree}.
\end{frame}

\begin{frame}
\frametitle{Ukkonen's tree}
Ukkonen's algorithm builds online the compressed suffix tree of a string. The algorithm requires $O(\log |\Sigma|)$ amortized time to append one letter to a string over alphabet $\Sigma$.

\begin{figure}[h]
\centering
\includegraphics[scale=0.5]{suffixTree}
\caption{A suffix tree for ``aacba''.}
\end{figure}
\end{frame}

\begin{frame}
Ukkonen's algorithm efficiently implements the parameter $minUniqueSuff$: the length of the minimal suffix of the processed string such that this suffix occurs in this string only once (Ukkonen, 1995).

\vspace{1em}
We don't interest in suffix tree itself we only need $minUniqueSuff$ to verify whether the suffix of a string has another occurrence in this string.
\end{frame}

\begin{frame}
\frametitle{Example}
Consider the string $w=abadaac$ and the sequence of calls $AddLetter(w[j])$, $UkkAlg(w[j])$, $j=1..7$ where call to $UkkAlg$ appends the letter to the suffix tree and maintains $minUniqueSuff$. The variables $n$, $text$, $i$, $Rad$ are the same as in Manacher's algorithm for odd palindromes.

\hrulefill

\begin{tabular}{llllll}
n & $text[1..n]$ & $text[i{-}Rad[i]..n]$ & $i$ & $Rad$ & $minUniqueSuff$\\
1 & a & a & 1 & (0) & 1\\
2 & ab & b & 2 & (0,0) & 1\\
3 & aba & aba & 2 & (0,1) & 2\\
4 & abad & d & 4 & (0,1,0,0) & 1\\
5 & abada & ada & 4 & (0,1,0,1) & 2\\
6 & abadaa & a & 6 & (0,1,0,1,0,0) & 2\\
7 & abadaac & c & 7 & (0,1,0,1,0,0,0) & 1
\end{tabular}
\end{frame}


\section{Lower Bounds}

\begin{frame}
\frametitle{Insert-only dictionary}
Recall that a \emph{dictionary} is a data structure $D$ containing some set of elements and designed for the fast implementation of basic operations like checking the membership of an element in the set, deleting an existing element, or adding a new element.

\vspace{1em}
\uncover<2->{We consider an \emph{insert-only dictionary over a set $S$}. In each moment, such a dictionary $D$ contains a subset of $S$ and supports only the operation $\mathrm{insqry}(x)$. This operation checks whether the element $x\in S$ is already in the dictionary; if no, it adds $x$ to the dictionary.}

\vspace{0.5em}
\uncover<3->{\begin{lemma}
Suppose that the alphabet $\Sigma$ consists of indivisible elements, $n\ge |\Sigma|$, and the insert-only dictionary $D$ over $\Sigma$ is initially empty. Then the sequence of $n$ calls of $\mathrm{insqry}$ requires, in the worst case, $\Omega(n\log|\Sigma|)$ time if $\Sigma$ is ordered and $\Omega(n|\Sigma|)$ if $\Sigma$ is unordered.
\end{lemma}}
\end{frame}

\begin{frame}
\begin{itemize}
\item We prove the required lower bounds reducing the problem of maintaining an insert-only dictionary to counting distinct palindromes in a string.
\item<2-> We assume that we have a black box algorithm that processes an input string letter by letter and outputs, after each step, the number of distinct palindromes in the string read so far.
\item<3-> We can assume that the considered black box algorithm works in time $O(n\cdot f(m))$, where $m$ is the size of the alphabet of the processed string and the function $f(m)$ is non-decreasing.
\end{itemize}
\end{frame}


\begin{frame}
\begin{lemma}
Suppose that $a,b$ are two different letters and $w=abx_1abx_2\cdots abx_n$ is a string such that each $x_i$ is a letter different from $a$ and $b$. Then all nonempty subpalindromes of $w$ are single letters.
\end{lemma}
\end{frame}


\begin{frame}
\frametitle{Maintaining an insert-only dictionary}
Let us describe how to process a sequence of $n$ calls $\mathrm{insqry}(x_1),\ldots,\mathrm{insqry}(x_n)$ starting from the empty dictionary. Suppose that $x_i \notin \{a,b\}$ for every $i$.

\begin{itemize}
\item<2-> We feed the black box with $a$, $b$, and $x_i$ (in this order). 
\item<3-> We get the output of the black box and check whether the number of distinct subpalindromes in its input string increased.
\item<4-> By Lemma, the increase happens if and only if $x_i$ appears in the input string of the black box for the first time. Thus, we can immediately answer the query ``$x_i\in D$?'', and, moreover, $x_i$ is now in the dictionary.
\end{itemize}

\uncover<5->{The overall time bound is $O(n\cdot f(m))$. We obtain $f(m)=\Omega(\log m)$ (resp., $f(m)=\Omega(m)$) in the case of ordered (resp., unordered) alphabet $\Sigma$.}
\end{frame}

\section{Conclusion}

\begin{frame}
\frametitle{Conclusion}
Our approach shows that it is hardly possible to design a linear time and space online algorithm for the discussed problem even in stronger natural computation models such as the word-RAM model or cellprobe model. The reason is the resource restrictions of dictionaries. However, up to the moment we have proved no nontrivial lower bounds for the insert-only dictionary in more sophisticated models than the comparison based model.
\end{frame}

\begin{frame}
\center{\Huge{Thank you for your attention!}}
\end{frame}

\end{document}